package leetcode101.data_structure;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Synhard
 * @version 1.0
 * @class Code14
 * @description 149. 直线上最多的点数
 * 给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。
 *
 * 示例 1:
 *
 * 输入: [[1,1],[2,2],[3,3]]
 * 输出: 3
 * 解释:
 * ^
 * |
 * |        o
 * |     o
 * |  o  
 * +------------->
 * 0  1  2  3  4
 * 示例 2:
 *
 * 输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
 * 输出: 4
 * 解释:
 * ^
 * |
 * |  o
 * |     o        o
 * |        o
 * |  o        o
 * +------------------->
 * 0  1  2  3  4  5  6
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-05-14 8:58
 */
public class Code14 {
    public static void main(String[] args) {
//        int[][] nums = new int[][]{{0,1},{0, 0}};
//        int[][] nums = new int[][]{{1,1},{2,2},{3,3}};
//        int[][] nums = new int[][]{{0,0},{4,5},{7,8},{8,9},{5,6},{3,4},{1,1}};
//        int[][] nums = new int[][]{{2, 3}, {3, 3}, {-5, 3}};
        int[][] nums = new int[][]{{0,0},{1, -1},{1, 1}};
        System.out.println(maxPoints(nums));
    }

    public static int maxPoints(int[][] points) {
        HashMap<Double, Integer> map = new HashMap<>();
        int dx, dy, same,nan, max = 0, value;
        double temp;
        for (int i = 0; i < points.length; i++) {
            same = 0;
            nan = 0;
            for (int j = i + 1; j < points.length; j++) {
                dx = points[i][0] - points[j][0];
                dy = points[i][1] - points[j][1];
                if (dx == 0) {
                    if (dy == 0) { // 说明是相同点
                        same++;
                        continue;
                    }
                    // 说明在同一垂直方向上
                    nan++;
                    continue;
                }
                temp = (double) dy / dx + 0.0;

                if (map.get(temp) == null) {
                    map.put(temp, 1);
                } else {
                    map.put(temp, map.get(temp) + 1);
                }
            }

            for (Map.Entry<Double, Integer> e : map.entrySet()) {
                value = e.getValue();
                max = Math.max(max, value);
            }
            max = Math.max(max, nan);
            max += same;
            map.clear();
        }
        max += 1;
        return max;
    }
}
/*
用hashmap来解决
对于每个点构造一个hashmap存储和他不同斜率的点数
斜率 ： 点数
注意每次构造需要单独保存与之相同的点的个数
以及斜率不存在的点的个数
最后取最大
注意double中的-0.0和0.0是两个数，如果要统一的话在结果中加上0.0
 */